package com.zk.algorithm.array;

import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.annotation.Medium;

/**
 * https://leetcode.com/problems/increasing-triplet-subsequence/
 * 返回数组中是否存在一个长度为 3 的连续递增自序列
 */
@LeetCodeExplore("334")
@Medium
public class IncreasingTripletSubsequence {

    public boolean increasingTriplet(int[] nums) {
        // start with two largest values,
        // as soon as we find a number bigger than both,
        // while both have been updated, return true.
        int small = Integer.MAX_VALUE,
                medium = Integer.MAX_VALUE;

        for (int n : nums) {
            if (n <= small) {
                small = n;
            } // update small if n is smaller than both
            else if (n <= medium) {
                medium = n;
            } // update big only if greater than small but smaller than big
            else
                return true; // return if you find a number bigger than both
        }

        return false;
    }

}